PsL Monthly 1993 December/PSL Monthly Shareware CD-ROM (December 1993).iso/prgmming/dos/c/comnumb.exe/RATIONAL.CPP

C/C++ Source or Header | 1992-05-01 | 9.9 KB | 399 lines

////////////////////////////////////////////////////////////////
// rational.cpp: Rational number class implementation.
// Copyright(c) 1992 Azarona Software. All rights reserved.
// NOTE: Many of the routines here could be made inline for
// significant performance gains.
////////////////////////////////////////////////////////////////
#include <ctype.h>
#include "rational.h"

long Gcd(long n, long d)
// Returns the greatest common divisor of |n| and |d|.
// Note: This routine will return 0 if both n and d are zero.
{
  if (n < 0) n = -n;
  if (d < 0) d = -d;
  while(d > 0) {
    long r = n % d;
    n = d;
    d = r;
  }
  return n;
}

istream &operator>>(istream &s, Rational &r)
// Reads in a rational number either as <n/d> or w,
// where w is a whole number. Appropriate whitespace
// is allowed. If the stream s is not in a good state upon
// return, then r will contain <0/0>.
{
  char c;

  if (s >> c) { // Read in first non-whitespace character
     if (isdigit(c) || (c == '-') || (c == '+')) {
        // We have a whole number. Put back character
        // and then read in the whole number.
        s.putback(c);
        if (s >> r.n) {
           r.d = 1; // Now we have proper fraction
        }
     }
     else if (c == '<') {
        // Reading in <n/d> syntax
        if (s >> r.n) { // We've got numerator
           if (s >> c) { // Look for '/'
              if (c == '/') {
                 if (s >> r.d) { // We've got denominator
                     r.Simplify();
                     if (s >> c) { // Look for '>'
                        // Syntax error?
                        if (c != '>') s.clear(ios::failbit);
                     }
                 }
              }
              else {
                s.clear(ios::failbit); // Signal syntax error
              }
           }
        }
     }
     else s.clear(ios::failbit); // Signal syntax error
  }
  if (!s) { // Stream failure, so result is undefined
     r.n = 0; r.d = 0;
  }
  return s;
}

ostream &operator<<(ostream &s, const Rational &r)
// Output rational number r to stream. Outputs "und"
// for <0/0>. If denominator is 1, it is not shown.
{
  if (r.d == 0) return s << "und";  // Undefined number
  if (r.d == 1) return s << r.n;    // Output whole number
  return s << '<' << r.n << '/' << r.d << '>';
}

Rational::Rational()
// Default constructor sets the number to be undefined.
: n(0), d(0)
{
  // Nothing else to do
}

Rational::Rational(long u)
// Rational number becomes whole number u.
: n(u), d(1)
{
  // Nothing else to do
}

Rational::Rational(long u, long v)
// General constructor initializing number to <u/v>.
{
  Set(u, v);
}

Rational::Rational(const Rational &r)
// Copy constructor.
: n(r.n), d(r.d)
{
  // Nothing else to do
}

long Rational::Numerator() const
{
  return n;
}

long Rational::Denominator() const
{
  return d;
}

int Rational::IsUndefined() const
{
  return d == 0;
}

int Rational::IsPositive() const
{
  return n > 0;
}

int Rational::IsNegative() const
{
  return n < 0;
}

int Rational::IsZero() const
{
  return n == 0 && d != 0;
}

void Rational::Simplify()
// Simplifies the rational number to have the smallest numerator
// and denominator possible. Also, if the number is negative,
// the numerator carries the sign. Also, all numbers of the
// form <x/0> are normalized to <0/0>, which represents
// "undefined".
{
  if (d != 0) {
    // Simplify the numerator and denominator
    long gcd = Gcd(n, d);
    n /= gcd;
    d /= gcd;
    if (d < 0) {
       // Keep negative sign in numerator. This also has
       // a nice side effect of eliminating the sign if
       // both n and d are negative.
       n = -n;
       d = -d;
    }
  }
  else n = 0; // So we have <0/0>
}

void Rational::Set(long u, long v)
// Sets rational number to <u/v>, simplifying
// the result.
{
  n = u; d = v; Simplify();
}

void Rational::Negate()
// Take the negative of this number.
{
  n = -n;
}

void Rational::Invert()
// Flip numerator and denominator
{
  long t = n;
  if (n < 0) { // Keep sign in numerator
     n = -d;
     d = -t;
  }
  else {
     n = d;
     d = t;
  }
  if (d == 0) n = 0; // Might have <x/0>, so set to <0/0>
}

long Rational::RemoveWholePart()
// If |this| > 1, remove the whole number part,
// so that |this| < 1. Return the whole number.
{
  long w;
  if (d == 0) { // Undefined number
     w = 0;     // (w can be anything, why not zero?)
  }
  else {
    w = n / d; // Get whole part...
    n -= w*d;  // Remove from number.
  }
  return w;
}

Rational &Rational::operator=(const Rational &r)
// Assignment operator.
{
  n = r.n; d = r.d; return *this;
}

Rational Rational::operator-() const
// Unary - operator. Computes negative of this number
// and returns a copy.
{
  return Rational(-n, d);
}

Rational Rational::operator+() const
// Unary + operator. Returns a copy of this number.
// (Thus, semantics are consistent with unary -).
{
  return Rational(*this);
}

Rational &Rational::operator+=(const Rational &r)
// Adds r to this number. Stores the result in this number.
{
  return operator=(*this + r);
}

Rational &Rational::operator-=(const Rational &r)
// Subtracts r from this number. Stores the result in
// this number.
{
  return operator=(*this - r);
}

Rational &Rational::operator*=(const Rational &r)
// Mutliplies this number by r. Stores the result in
// this number.
{
  return operator=(*this * r);
}

Rational &Rational::operator/=(const Rational &r)
// Divides this number by r. Stores the result in
// this number.
{
  return operator=(*this / r);
}

Rational &Rational::operator++()
// Prefix increment operator. Safe to use
// in expressions like ++(++r).
{
  return *this += 1;
}

Rational &Rational::operator--()
// Prefix decrement operator. Safe to use
// in expressions like --(--r).
{
  return *this -= 1;
}

Rational Rational::operator++(int)
// Postfix increment. Note that we don't return a reference
// as we do with prefix increment. Instead a copy of the result
// is returned. Thus, expressions like (r++)++ will not return
// the correct result.
// WARNING: Result not checked for possible overflow.
{
  Rational old(*this);
  *this += 1;
  return old;
}

Rational Rational::operator--(int)
// Postfix decrement. Note that we don't return a reference
// as we do with prefix decrement. Instead a copy of the result
// is returned. Thus, expressions like (r--)-- will not return
// the correct result.
// WARNING: Result not checked for possible overflow.
{
  Rational old(*this);
  *this -= 1;
  return old;
}

Rational operator+(const Rational &a, const Rational &b)
// Adds a to b and returns the result. See Knuth Vol 2 for
// explanation on the method used here to do the addition,
// which carefully avoids (but does not eliminate) overflow.
// This method also automatically simplifies the result.
// If one operand is undefined, the result is undefined.
// WARNING: Result not checked for possible overflow.
{
  Rational r;
  long t, d1, d2;

  if (a.d == 0 || b.d == 0) { // Undefined operand?
     r.n = 0; r.d = 0; // So we have <0/0>
  }
  else {
    d1 = Gcd(a.d, b.d);
    if (d1 == 1) {
       r.n = a.n*b.d + a.d*b.n;
       r.d = a.d*b.d;
    }
    else {
       t = a.n*(b.d/d1) + b.n*(a.d/d1);
       d2 = Gcd(t, d1);
       r.n = t / d2;
       r.d = (a.d/d1) * (b.d/d2);
    }
  }
  return r;
}

Rational operator-(const Rational &a, const Rational &b)
// Subtracts b from a and returns result. Uses the
// operator+() function to do the dirty work.
// WARNING: Result not checked for possible overflow.
{
  Rational nb(b); // Note: We are avoiding a call to
  nb.Negate();    // Simplify() here.
  return a + nb;  // Ie: a + (-b)
}

Rational operator*(const Rational &a, const Rational &b)
// Multiplies a and b together and returns result.
// Method used is ala Knuth: Vol. 2, which carefully
// avoids (but does not eliminate) overflow. This
// method also automatically simplifies the result.
// Note that an undefined operand yields an undefined
// result.
// WARNING: Result not checked for possible overflow.
{
  Rational r;
  long d1, d2;
  if (a.d == 0 || b.d == 0) { // Undefined operand?
     r.n = 0; r.d = 0; // So that <0/0> is returned
  }
  else {
    d1 = Gcd(a.n, b.d);
    d2 = Gcd(a.d, b.n);
    r.n = (a.n/d1) * (b.n/d2);
    r.d = (a.d/d2) * (b.d/d1);
  }
  return r;
}

Rational operator/(const Rational &a, const Rational &b)
// Divides a by b, returning the result. Note that
// operator*() does all the dirty work.
// WARNING: On divide by zero, an "undefined" result is
// returned, but no other forms of overflow are checked.
{
  Rational ib(b); // Note: We are avoiding a call to
  ib.Invert();    // Simplify() here.
  return a * ib;  // Ie: a * (1/b)
}

int operator==(const Rational &a, const Rational &b)
// Note: Assumes a & b are simplified.
{
  return a.n == b.n && a.d == b.d;
}


int operator!=(const Rational &a, const Rational &b)
// Inequality operator.
{
  return !(a == b);
}

int operator<(const Rational &a, const Rational &b)
// Returns 1 if a < b, else 0. Note that if either
// a and/or b is undefined, the result is 0.
{
  return a.n*b.d < a.d*b.n;
}

int operator<=(const Rational &a, const Rational &b)
// Note: Using !(operator>(a,b)) would not work for
// all cases. (Eg: if a and/or b are undefined.)
{
  return a == b || a < b;
}

int operator>(const Rational &a, const Rational &b)
// Returns 1 if a > b, else 0. Note that if either
// a and/or b is undefined, the result is 0.
{
  return a.n*b.d > a.d*b.n;
}

int operator>=(const Rational &a, const Rational &b)
// Note: Using !(operator<(a,b)) would not work for
// all cases. (Eg: if a and/or b are undefined.)
{
  return a == b || a > b;
}